// ml:run = $bin < input
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>

using ll = long long;
ll const mo = 1000000007;
int const maxn = 500;
int const maxp = 2007;
ll a[maxn];
ll c[maxn][maxn];
ll pow2[maxn];
std::vector<int> ap[maxn];
std::map<ll, int> fact_count;
int n;

bool not_prime[maxp];
std::vector<int> prime;

void init_prime()
{
    for (int i = 2; i < maxp; i++) {
        if (not_prime[i]) continue;
        prime.push_back(i);
        for (int j = 2 * i; j < maxp; j += i)
            not_prime[j] = true;
    }
}

void init()
{
    for (int i = 0; i < maxn; i++) ap[i].clear();
    fact_count.clear();
}

void init_c()
{
    pow2[0] = 1;
    for (int i = 1; i < maxn; i++)
        pow2[i] = (pow2[i - 1] * 2) % mo;

    c[0][0] = 1;
    for (int i = 1; i < maxn; i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mo;
    }
}

ll calc(int x)
{
    ll sum = 0;
    for (int i = 1; i <= x; i += 2) sum = (sum + c[x][i]) % mo;
    return (sum * pow2[n - x]) % mo;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    init_prime();
    init_c();
    int T; std::cin >> T;
    for (int ti = 1; ti <= T; ti++) {
        std::cout << "Case #" << ti << ":\n";
        std::cin >> n;
        init();
        int tn = n;
        for (int i = 1; i <= n; i++) {
            std::cin >> a[i];
            auto tmp = a[i];
            for (auto p : prime) {
                if (!(tmp % p)) {
                    int count = 0;
                    for (; !(tmp % p); count++) tmp /= p;
                    if (count & 1) ap[i].push_back(p);
                }
            }

            int len = ap[i].size();
            for (int st = 1; st < (1 << len); st++) {
                ll pro = 1;
                int count = 0;
                for (int j = 0; j < len; j++)
                    if ((st >> j) & 1) {
                        pro *= ap[i][j];
                        count++;
                    }
                if (st == (1 << len) - 1) a[i] = pro;
                fact_count[pro]++;
            }
        }

        ll ans = 0;
        for (auto it = fact_count.rbegin(); it != fact_count.rend(); ++it) {
            std::cerr << it->first << " " << it->second << " " << calc(it->second) << "\n";
            if (!it->second) continue;
            ans += calc(it->second);
            int tmp = it->second;
            ans %= mo;
            for (int i = 1; i <= tn; i++) {
                if (a[i] == it->first) {
                    int len = ap[i].size();
                    for (int st = 1; st < (1 << len); st++) {
                        ll pro = 1;
                        for (int j = 0; j < len; j++)
                            if ((st >> j) & 1) {
                                pro *= ap[i][j];
                            }
                        fact_count[pro]--;
                    }
                }
            }
            n -= tmp;
        }
        ans = (pow2[tn] - 1 - ans) % mo;
        ans = (ans + mo) % mo;
        std::cout << ans << "\n";
    }
}

